package com.zj.study;

public class 最短路径问题floyd {

    private static final int MAX = 99;

    public static void main(String[] args) {
//        int[][] arr={
//                {0,4,6,6,MAX,MAX,MAX},
//                {MAX,0,1,MAX,2,MAX,MAX},
//                {MAX,MAX,0,MAX,6,4,MAX},
//                {MAX,MAX,2,0,MAX,5,MAX},
//                {MAX,MAX,MAX,MAX,0,MAX,6},
//                {MAX,MAX,MAX,MAX,1,0,8},
//                {MAX,MAX,MAX,MAX,MAX,MAX,MAX}
//        };

        int[][] arr = {
                {0, MAX, MAX, MAX},
                {1, 0, 1, MAX},
                {MAX, MAX, 0, 1},
                {MAX, MAX, MAX, 0}

        };
//注意最外层必须是中间顶点，否则结果不准确。
        for (int k = 0; k < arr.length; k++) {
            for (int i = 0; i < arr.length; i++) {
                for (int j = 0; j < arr.length; j++) {
                    if (arr[i][k] + arr[k][j] < arr[i][j]) {
                        arr[i][j] = arr[i][k] + arr[k][j];
                    }
                }
            }
        }

        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(arr[i][j] + "\t\t\t\t");
            }
            System.out.println();
        }

    }
}
